This invention relates to binning apparatus for generating a histogram of input values of data relating to physical phenomena such as parameters of imaging devices, and to a method for binning input values so as to generate such a histogram.
The processing pipelines of digital cameras frequently make use of histograms to summarise the frequency distribution of parameters, such as exposure parameters, captured by the pixels of the camera sensor. A histogram divides the range of possible input values of a parameter into a series of bins, with each bin representing a count of the number of pixels having a parameter falling within the respective range of that bin. Such histograms can be used by the image processing algorithms of the pipeline in order to perform control functions of the camera such as auto-exposure, auto-focus and auto-white balance. A camera sensor will generally include many millions of pixels and the use of such histograms helps to provide a summary of the characteristics of a captured frame at a level of detail which is appropriate and manageable by pipeline algorithms.
A problem is encountered with the use of conventional binning controllers in digital cameras to generate such histograms, especially when the frequency distribution of the frame parameter exhibits sharp changes in value. For example, in the case where the parameter is a measure of exposure, this can be seen when a large number of pixels all indicate exposure parameters lying within a narrow range. FIG. 3 illustrates such a clustering of exposure parameters, which presents as a sharp spike 303 in the frequency distribution of exposure parameters reported by the pixels of the frame (only part of that distribution is illustrated in the figure). In practice, this might be observed when, for example, a camera captures a frame that includes a large area of brightly-lit white wall (such as behind a person who is having their portrait taken). Such a frame would exhibit a spike in the frequency distribution at a high exposure corresponding to the bright white areas of the captured frame.
In FIG. 3, bins 301 and 302 are adjacent bins forming part of a histogram generated from the frequency distribution of the captured exposure parameters. The frequency distribution can represent the frequency of occurrence of captured exposure parameters in a given sample (a sample being, for example, a set of captured exposure parameters belonging to a frame captured by a camera sensor). A frequency distribution can be represented by a table having entries for each of a set of intervals which collectively span the range of possible values of the captured exposure parameters, each entry in the table holding a count of the number of occurrences of captured exposure parameters which have values that lie within the respective interval.
It can be seen in FIG. 3 that the width of the spike 303 is narrower than the width of adjacent bins 301 and 302 of the histogram. In forming the histogram, all of the exposure parameters lying within the range of bin 301 (to the right side of line 304) would be allocated to bin 301, and all of the exposure parameters lying within the range of bin 302 (to the left side of line 304) would be allocated to bin 302. Bin 302, in which the peak of the spike lies, therefore receives a significantly higher contribution than bin 301.
However, as each consecutive frame is captured by the camera and the light incident at the sensor changes (e.g. due to repositioning of the camera or changes in the captured scene), the spike is likely to shift slightly from one frame to the next whilst the auto-exposure algorithms are looking to optimize the exposure of the frame to be captured. As can be appreciated from FIG. 3, only a small shift in the position of spike 303 is required to move it from bin 302 into bin 301. Roughly speaking, this would cause the peak in the histogram to move from bin 302 to bin 301, substantially changing the profile of the histogram. Small shifts in the position of a spike in the frequency distribution of an exposure parameter can in other words be amplified, leading to large changes in the histogram and consequent changes e.g. to the decisions made by the auto-exposure control function of the digital camera.
For example, consider the case in which the spike 303 shifts by a small amount from bin 302 to 301. The value of each bin of a histogram is typically taken to be the mean value of that bin (e.g. central values 305 and 306 in FIG. 3). The value of the peak initially represented by bin 302 prior to the shift in the spike 303 therefore takes a value of 306, but following the shift in the spike 303 the peak appears to occur at the value 305, which is the mean value of bin 301. Movements of the spike 303 of significantly less than the width of a bin can therefore lead to a step change in the apparent location of a peak (as indicated by the histogram) equal to the width of a bin.
A particular manifestation of this problem is that when a spike in an exposure parameter occurs close to the boundary between the bins of a histogram, the auto-exposure (AE) control function of the digital camera can end up oscillating between states. For example, the AE function might select a first mode when the histogram generated by a conventional binning controller appears to show a peak at bin 302. In response, the AE function could adapt control parameters such as shutter speed and sensitivity which in turn might cause the spike 303 to shift slightly in the manner described above and hence result in the histogram showing a peak at bin 301. The auto-exposure algorithm would in response then select a second mode and adapt the control parameters in a different way, shifting the underlying spike 303 back into bin 302. In this manner, conventional binning controllers can suffer from feedback issues which cause the control algorithms of digital cameras to oscillate between modes even in the absence of environmental changes such as changes in light levels in the captured scene. This can lead to sub-optimal camera performance and excessive power consumption by the device.
Such problems with conventional binning controllers are typically addressed by introducing a greater number of bins. However, this has the effect of significantly increasing the resources required by the binning apparatus because the complexity of the binning controller is increased, the resources consumed by the bins is increased, and the complexity of control algorithms using the histogram output of the binning controller is increased.